#include<bits/stdc++.h>
#include<ctime>

using namespace  std;

template<typename T>
T fast_pow(T base, T exponent, T modulus) {
    T result = 1; // 初始化结果为1
    while (exponent > 0) { // 当指数大于0时，执行循环
        if (exponent & 1) { // 如果指数是奇数
            result *= base; // 将结果乘以底数
            result %= modulus; // 对结果取模
        }
        base *= base; // 将底数自乘
        base %= modulus; // 对底数取模
        exponent >>= 1; // 将指数右移一位（相当于除以2）
    }
    return result; // 返回结果
}
template<typename T>
vector<T> primeSieve(T n){
    vector<bool> isPrime(n + 1,true); // 标记是否为素数
    vector<T> primes; // 存储素数
    isPrime[0] = isPrime[1] = false; // 0和1不是素数
    for(T i = 2 ; i * i <= n; ++i){   // 线性筛素数
        if(isPrime[i]){      // 将i的倍数标记为非素数
            for(T j = i * i;j <= n;j += i){
                isPrime[j] = false;
            }
        }
    }
    for(T i=2;i<=n;++i){    // 将素数加入primes列表
        if(isPrime[i]){
            primes.push_back(i);
        }
    }
    return primes;
}
int main() {
    vector<int> p = primeSieve(1000);
    for(auto x: p) cout << x <<endl;

    return 0;
}
